/**
 * 
 */
package string.passed;

/**
 * @author xyyi
 *
 */
public class StrStr {

	/**
	Implement strStr().

	Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
	
	KMP Solution
	http://www.matrix67.com/blog/archives/115
	 */
	public String strStr(String str, String target) {

		if (target == null || target.isEmpty())
			return target;

		if (str == null || str.isEmpty())
			return null;

		int[] next = buildNext(target.toCharArray());
		int ti = -1;
		for (int si = 0; si < str.length(); si++) {
			while (ti >= 0 && target.charAt(ti + 1) != str.charAt(si))
				ti = next[ti];
			if (target.charAt(ti + 1) == str.charAt(si))
				ti++;
			if (ti == target.length() - 1)
				return str.substring(si - target.length() + 1);
		}

		return null;
	}

	// next[k] : if k + 1 is not match, the target start position
	private int[] buildNext(char[] str) {
		assert (str != null && str.length > 0);

		int[] next = new int[str.length];
		int pre = -1;
		next[0] = pre;
		for (int curr = 1; curr < next.length - 1; curr++) {
			while (pre >= 0 && str[pre + 1] != str[curr])
				pre = next[pre];
			if (str[pre + 1] == str[curr])
				pre++;
			next[curr] = pre;
		}

		return next;
	}

	/**
	 * 
	 */
	public StrStr() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		StrStr ss = new StrStr();
		String str = "mississippi";
		String target = "issipi";
		ss.strStr(str, target);

	}

}
